\chapter{古典密码(Classical Encryption)}
这部分我们介绍一下古典密码。
\begin{note}
	问：什么是古典\par
	答：很早以前的\par
	问：多早以前的\par
	答：What？Can u speak English？\footnote{“古典”本身就是一个模糊的定义，通常我们认为香农经典论文发表之前的为"古典"，或者利用香农的基本思想设计的密码系统将不是“古典密码”.}
\end{note}


\section{简单替换密码(Simple Substitution Cipher )\cite{shannon-secrecy}}
在这种密码中，消息中的每个字母都被一个固定的替代字母代替，通常也是一个字母。消息：
\[M=m_1 m_2 m_3 m_4\cdots\]
此处$m_1,m_2,\cdots$是连续的字母，变成：
\begin{equation}
\begin{aligned}
E &=e_1 e_2 e_3 e_4 \cdots \\
&= f(m_1)f(m_2)f(m_3)f(m_4)\cdots\nonumber
\end{aligned}
\end{equation}
此处$f(m)$函数有逆函数，密钥是字母表的排列（当替代物是字母时），例如:\\
$X G U A C D T B F H R S L M Q V Y Z W I E J O K N P$\\
在这个例子中，第一个字母$X$是$A$的替代物，$G$是$B$的替代物等。

\section{换位(固定周期d)(Transposition (Fixed Period d))\cite{shannon-secrecy}}
消息被分为长度为$d$的组，有一个置换作用于第一组，相同置换作用于第二组，以此类推。置换是密钥，可以由前$d$个整数的置换表示。因此，对于d=5，我们可能有2 3 1 5 4作为置换。这意味着：
\begin{equation}
\begin{aligned}
&m_1\ m_2\ m_3\ m_4\ m_5\textbrokenbar \ m_6\ m_7 \ m_8 \ m_9 \ m_{10}\textbrokenbar \cdots\text{becomes} \\
&m_2\ m_3\ m_1\ m_5\ m_4\textbrokenbar \ m_7\ m_8 \ m_6 \ m_{10} \ m_9\textbrokenbar \cdots\nonumber
\end{aligned}
\end{equation}
两个或多个转置的顺序应用将被称为复合转置(compound transposition)。如果周期为$d_1,\cdots,d_s$，很明显，结果是周期$d$的转置，其中$d$是$d_1,\cdots,d_s$的最小公倍数。

我们用下面一张图来解释加密过程:
\begin{figure}[htb]
	\includegraphics[width=0.8\textwidth]{transpostion-fixedp.png}
\end{figure}


\section{凯撒密码Caesar cipher}
	\begin{equation}
		\begin{cases}
		c=m+3(mod\ 26) \quad 0\leq m \leq 25 \\
		m=c-3(mod\ 26) \quad 0\leq c \leq 25 
		\end{cases}
	\end{equation}
	
\vspace{1cm}
\begin{example}
	利用凯撒密码对"LI XIAO FENG SHI LAO SHI"进行加密。
\end{example}
\begin{solution}
	首先需加密的都是大写，我们使用Ascii码对其编码，并且去掉空格，变为"LIXIAOFENGSHILAOSHI",
	A$\sim$Z的Ascii码为65$\sim$90，所以计算时编码要减去65。
\end{solution}
\vspace{1cm}

\section{移位变换(shift transformation)/加法密码}
	\begin{equation}
		\begin{cases}
			c=m+k(mod\ 26),m \geq 0 ,k \leq 25 \\
			m=c-k(mod\ 26),c \geq 0 ,k \leq 25
		\end{cases}
	\end{equation}

\section{Vigen\`{e}re及其变种(Vigen\`{e}re and Variations )\cite{shannon-secrecy}}
在维格纳密码中，密钥由$d$个字母序列组成。这些字母在消息下方重复书写，消息和密文模26加（考虑字母表编号从$A=0到Z=25$）,即
\[ e_i = m_i+k_i(mod\ 26) \]
此处$k_i$在索引$i$中为周期$d$,例如，密钥为$G\ A\ H$,我们可以得
\begin{equation}
\begin{aligned}
message\ &N\ O\ W\ I\ S\ T\ H\ E\ &\cdots\\
repeated\ key\ &\underline{G\ A\ H}\ \underline{G\ A\ H}\ \underline{G\ A\ H}\ G\ A\ &\cdots\\
cryptgram\ &T\ O\ D\ O\ S\ A\ N\ E\ &\cdots\nonumber
\end{aligned}
\end{equation}


上面的计算过程，我们解释一下，首先我们要获得字母对应的数字：\par
\begin{tabular}{|c|c|c|c|c|c|}
	\hline 
	A=0& B=1 & C=2 & D=3 & E=4 & F=5 \\ 
	\hline 
	G=6& H=7 & I=8 & J=9 & K=10 & L=11 \\ 
	\hline 
	M=12& N=13 & O=14 & P=15 & Q=16 & R=17 \\ 
	\hline 
	S=18& T=19 & U=20 & V=21 & W=22 & X=23 \\ 
	\hline 
	Y=24& Z=25 &  &  &  &  \\ 
	\hline 
\end{tabular} 
\par
那么上面的方程就可以写成\par
\begin{equation}
\begin{aligned}
message\ &13\ &14\    &22\ &8\ &18\ &19\ &7\ &4\ &\cdots\\
repeated\ key\ &6\ &0\ &7\ &6\ &0\ &7\   &6\ &0\ &\cdots\\
cryptgram\ &19\ &14\   &3\ &14\ &18\ &0\ &13\ &4\ &\cdots\nonumber
\end{aligned}
\end{equation}

\par

周期1的Vigen\`{e}re被称为凯撒密码。它是一种简单的替换，其中$M$的每个字母在字母表中前进一个固定的量。这个量是密钥，可以是从0到25的任何数字。所谓的波弗特(Beaufort)和变异波弗特(Variant Beaufort)类似于维格纳(Vigen\`{e}re)，这两种方式分别通过以下方程加密
\[e_i=k_i-m_i(mod\ 26)\]
和
\[e_i=m_i-k_i(mod\ 26).\]

周期为1的波弗特(Beaufort)密码被称为反向凯撒密码。

两个或多个Vigen\`{e}re按顺序的应用将被称为复合Vigen\`{e}re，公式为
\[e_i=m_i+k_i+l_i+\cdots + s_i(mod\ 26)\]
此处$k_i,l_i,\cdots,s_i$通常有不同的周期，它们的和$k_i+l_i+\cdots+s_i$的周期,做为一个复合变换，是各周期的最小公倍数。

当Vigen\`{e}re使用一个没有限制的密钥时，且永不重复，我们有这样一个Vigen\`{e}re系统\footnote{G . S . Vernam ,“ Cipher Printing Telegraph Systems for Secret Wire and Radio Telegraphic Communications , ” Journal American Institute of Electrical Engineers , v . XLV ,pp . 109 - 115 , 1926.}
\[e_i=m_i+k_i(mod\ 26)\]
$k_i$是在$0,1,\cdots,25$中随机和独立选择的。如果密钥是有意义的文本，我们称其为“运行密钥”( running key)密码。\footnote{注：“有意义的文本”是指一个单词或者一个短语，比如密钥是"little boy"之类的。}

\section{乘法密码}
	\begin{equation}
		\begin{cases}
			c=am \pmod{26} \\
			m=bc \pmod{26},b=a^{-1} \pmod{26}
		\end{cases}
	\end{equation}

\section{仿射变换(affine transformation)}
	\begin{equation}
      \begin{cases}
        c=am+b(mod\ 26) \\
        m=a^{-1}(c-b)(mod\ 26),&a \geq 0,b \leq 25,gcd(a,26)=1,a^{-1}a=1 mod \ 26 
      \end{cases}
    \end{equation}
    仿射变换中a，b是密钥。
    
\section{多表代换密码}
多表代换密码首先将明文M进行分组，每组长度为n个字母\footnote{注意分组密码时的填充问题，也就是说当最后一组不够n的长度时，需要补齐，补齐时需要考虑，解密方在解密后，如何知道是补齐的信息，还是原信息。}，分组后的明文序列表示为$M_1,M_2,\ldots,M_f$,$M_i(i=1,2,\ldots,f)$表示分组消息，加密为：\[C_i=AM_i+B \pmod{N},i=1,2,\ldots,f\]
其中A是$n\times n$可逆矩阵，满足$gcd(|A|,N)=1$,|A|表示矩阵A的行列式，B为$n\times 1$矩阵，$M_i$为一分组的$n\times 1$矩阵表示，$C_i$是加密后所得密文分组的$n\times 1$矩阵表示。对密文分组的解密为：\[M_i=A^{-1} (C_i-B) \pmod{N}\]
\par
通常对字母进行加密时，$N=26$。

\subsection{游乐场密码(The Playfair Cipher)\cite{shannon-secrecy}}

这是一种特殊类型的二元图替换，将乱序的25个字母写在$5\times 5$的正方形中。（字母J在密码工作中经常被丢弃,因为J很少见，当它出现时，可以用I代替。）假设密钥正方形如下所示：

\begin{equation}
\begin{array}{ccccc}
L &Z &Q &C &P\\
A &G &N &O &U\\
R &D &M &I &F\\
K &Y &H &V &S\\
X &B &T &E &W \nonumber
\end{array} 
\end{equation}


例如，数字符号AC的替代物是由A和C定义的矩形的其他两个角上的一对字母，即LO，首先取L，因为它在A之上。如果数字符号与RI在一条水平线上，则使用右边DF的字母；RF变为DR。如果字母在垂直线上，则使用它们下面的字母，因此PS变为UW。如果字母相同，则可以使用空值来分隔它们，或者可以省略一个，等等。

\subsection{自动密钥密码(Autokey Cipher)\cite{shannon-secrecy}}

这是一种Vigen\`{e}re类型的系统，其中消息本身或生成的密文被用作“密钥”，称为自动密钥密码。加密从“启动密钥”（在我们的意义上是整个密钥）开始，并继续使用消息或密文，其长度被启动密钥的长度所取代，如下所示，其中启动密钥是COMET。消息用作“密钥”：
\begin{equation}
\begin{aligned}
Message\qquad    &\uwave{SENDSUP}PLIES\cdots \\
Key\qquad        &\underline{COMET}\uwave{SENDSUP}\cdots \\
Crytorgram\qquad &USZHLMTCOAYH\cdots \nonumber
\end{aligned}
\end{equation}

如果用密文做“密钥”则是：\footnote{从保密的角度来看，这个系统是微不足道的，因为除了开头的d个字母，敌人拥有整个“密钥”.}
\begin{equation}
\begin{aligned}
Message\qquad    &SENDSUPPLIES\cdots \\
Key\qquad        &\underline{COMET}\uwave{USZHLOH}\cdots \\
Crytorgram\qquad &\uwave{USZHLOH}OSTS\cdots \nonumber
\end{aligned}
\end{equation}
